package likou;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/25 20:09
 */
public class _1609 {
    public boolean isEvenOddTree(TreeNode root) {
        TreeNode[] nodeStack = new TreeNode[100000];
        int level = -1;
        int top = -1;
        nodeStack[++top] = root;
        int currPos = -1;
        while (currPos < top) {
            int size = top - currPos;
            int lastVal = -1;
            level++;
            while ((--size) >= 0) {
                TreeNode node = nodeStack[++currPos];
                assert node != null;
                if ((level + node.val) % 2 == 0)
                    return false;
                if (lastVal != -1) {
                    if (level % 2 == 0) {
                        if (lastVal >= node.val)
                            return false;
                    } else {
                        if (lastVal <= node.val)
                            return false;
                    }
                }
                lastVal = node.val;
                if (node.left != null)
                    nodeStack[++top] = node.left;
                if (node.right != null)
                    nodeStack[++top] = node.right;
            }
        }
        return true;
    }
}
